package LinkedList;//给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
//
// 你不需要 保留 每个分区中各节点的初始相对位置。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,4,3,2,5,2], x = 3
//输出：[1,2,2,4,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [2,1], x = 2
//输出：[1,2]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 200] 内 
// -100 <= Node.val <= 100 
// -200 <= x <= 200 
// 
// Related Topics 链表 双指针 👍 72 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class partition1 {
    public ListNode partition(ListNode head, int x) {
        /**
         * 将链表拆成两个链表，前面放小于目标值的，后面放大于等于目标值的
         * 需要4个指针
         * */
        // 确定两个链表的开始和结束指针
        ListNode smallHead = new ListNode(0);
        ListNode bigHead = new ListNode(0);
        ListNode smallTail = smallHead;
        ListNode bigTail = bigHead;
        //遍历链表
        while(head!=null){
            if(head.val<x){
                //放到小链表后面
                smallTail.next = head;
                smallTail = smallTail.next;
            }else{
                //放到小链表后面
                bigTail.next = head;
                bigTail = bigTail.next;
            }
            head = head.next;
        }
        //小链表和大链表 链接
        smallTail.next = bigHead.next;
        bigTail.next = null;
        return smallHead.next;
    }

    public ListNode partition1(ListNode head, int x) {
        /**
         * 链表排序，如果目标值在链表中，那么结果一定满足
         * 归并排序效率更佳
         * 不考虑原始顺序
         * */
        return mergeSort(head,null);
    }

    private ListNode mergeSort(ListNode head, ListNode tail) {
        //无法继续拆分的情况
        if (head == null) {
            return null;
        }
        //无法继续拆分的情况
        if (head.next == tail) {
            head.next = null;
            return head;
        }

        //快慢指针找到中间节点
        ListNode slow = head, fast = head;
        while (fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow;
        //左边继续拆分
        ListNode left = mergeSort(head, mid);
        //右边继续拆分
        ListNode right = mergeSort(mid, tail);
        //有序链表合并
        return merge(left, right);
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode mergeNode = new ListNode(0);
        ListNode help = mergeNode;
        //比较两个链表当前的值，值小的链表就把引用赋给mergeNode，并向后移动一位重新赋值给自己，同时help指向值小的那个节点
        while (left != null && right != null) {
            if (left.val < right.val) {
                help.next = left;
                left = left.next;
            } else {
                help.next = right;
                right = right.next;
            }
            help = help.next;
        }
        //最后如果有剩余的节点，就一次性链上去
        help.next = left == null ? right : left;
        return mergeNode.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
